This invention relates to the field of data processing, and, more particularly to an improved method and apparatus for converting color image data to a generally non-linear palette.
Color space and depth conversion is a long standing problem with image displaying applications because of the numerous options for both storage and display. A common format for color data storage is RGB16 where there are five bits of red significance, six bits of green significance, and five bits of blue significance. The format can be expressed as R5:G6:B5 and stored as one 16-bit word.
One format for a display is an 8-bit palette environment which is typically found in graphical user interfaces (GUIs). This type of environment defines 256 colors, where each color component generally has six bits of significance. The components are either RGB, YUV, or one of their many variations. With such a system, a maximum of 256 colors can be simultaneously defined on a screen. Hence, a conversion must be done by mapping the original 16-bit color data to one of the 256 available colors. Since most colors in an image tend to not exactly match one of the 256 available colors, artifacts will appear.
A very common artifact is called "contouring". Since an 8-bit display has only 256 distinct colors, a GUI will use a general palette that spans the entire color spectrum thus allowing any application needing to display a color to have a reasonable approximation to the desired color. A general palette typically results in a very quantized color space (i.e., large differences in incremental color shades may exist). When there is a gradual change of colors across an image such as blue skies, shadows, or facial tones, some colors in a region may map to one quantized color and other colors on the other side of the region may map to a different quantized color. This difference of colors is noticeable and results in visual lines or arcs, called "contour lines".
A known method of making contour lines less noticeable is to add ordered "noise" to the colors prior to conversion. The noise in effect changes how rounding to the closest quantized color is done such that an area of color between two palette entries is displayed by alternating the quantized colors of the two palette entries to create a sort of blurring mesh effect over the area. Although this method is somewhat effective, it requires substantially numerical computations thus making it unacceptable for software-only real-time video decompression and display. First, the converter must add the noise. For instance, if a 1 is added to the blue component of RGB16 format, there might be a carry into the green. Thus, a check must be made to see that the blue component will not carry into green prior to the addition. It is tempting to stop at this point and do the conversion. However, the only contour lines that are blurred are distinctly blue areas such as the sky, but not shadows nor facial tones. Furthermore, the color shifts towards the blue and produces a blue tint across the image. To compensate for this, equal amounts of noise need to be added to each color component to most closely preserve the original color. The final result is alternating brighter and darker pixels across the image. If the additive noise pattern is ordered diagonally such that the pixels alternate both horizontally and vertically, and the image has sufficient resolution (e.g., 640 by 480 pixels), then human perception tends to average the luminance difference and the alternating brighter and darker pixels are unlikely to be noticeable.
The additive noise pattern just described can be defined by the following 2.times.2 dither matrix:
______________________________________ 0 1 1 0 ______________________________________
A better quality dither matrix would have more levels of noise variation, such as:
______________________________________ 0 3 2 1 ______________________________________
A dither matrix such as the latter one, more closely approximates the desired color. However,its disadvantage is that the order of computational complexity of adding and clamping color components is significantly higher.
Another disadvantage of employing a routine that converts 16-bit color data to a palette, generally non-linear, is that 256 color comparisons must be made for every pixel on the screen. This is particularly true when the non-linearly quantized values of each (or any) of the three color primaries in the palette are not stored in a sorted sequence. Each color comparison entails the following: a subtract, a check for a negative result, a possible negate, a compare with the previous closest color's three components, a possible update, and loop control. Such procedure has to be performed 256 times for each pixel to be displayed (i.e., once for each of 256 colors in the palette). The complexity of such conversion may be too high for still image applications, and is unacceptable for software-only decompression and display of digital video on low-end platforms such as personal computers with 386 and 486 class microprocessors.